#include<iostream>
#include<vector>
using namespace std;

// 打印数组
void disp(vector<int> &a)
{
	for(int i=0; i<a.size(); i++)
		printf("%d ", a[i]);
	printf("\n");
}


// 在R[i..n-1]中冒泡最小元素到R[i]位置
void Bubble(vector<int>& R, int i, bool& exchange)
{
	// 计算数组长度
	int n=R.size();
	
	// 无序区元素比较,找出最小元素
	for (int j=n-1;j>i;j--)
		if (R[j-1] > R[j])	 // 当相邻元素反序时
		{
			swap(R[j], R[j-1]); // a[j]与a[j-1]进行交换
			exchange=true; // 本趟排序发生交换置exchange为true
		}
}


/* 迭代算法 */
// 迭代算法：冒泡排序
void BubbleSort1(vector<int>& R)	
{
	// 计算数组长度
	int n=R.size();
	bool exchange;
	
	// 进行n-1趟排序
	for (int i=0; i<n-1; i++)
	{
		// 本趟排序前置exchange为false
		exchange = false;
		Bubble(R, i, exchange);
		
		// 本趟未发生交换时，结束算法
		if (exchange==false)
			return;
	}
}


/* 先递后合算法 */
// 在R[i..n-1]中冒泡最小元素到R[i]位置
void Bubble1(vector<int>& R, int i)
{
	// 获取长度
	int n = R.size();
	
	// 无序区元素比较,找出最小元素
	for (int j=n-1; j>i; j--)
		if (R[j-1] > R[j]) // 当相邻元素反序时
			swap(R[j], R[j-1]); // R[j]与R[j-1]进行交换
}

// 递归的冒泡排序
void BubbleSort21(vector<int>& R, int i)	
{
	// 满足递归出口条件
	if (i==-1) return;
	
	// 递归调用 
	BubbleSort21(R, i-1);
	Bubble1(R, i);
}

// 递归冒泡排序 
void BubbleSort2(vector<int>& R)
{
	int n = R.size();
	BubbleSort21(R, n-2);
}

/* 先合后递算法 */
void BubbleSort31(vector<int>& R, int i)			// 递归的简单选择排序
{
	// 数组长度
	int n = R.size();
	
	// 满足递归出口条件
	if (i==n-1) return;
	Bubble1(R, i);
	
	// 递归调用 
	BubbleSort31(R, i+1);
}

// 递归冒泡排序
void BubbleSort3(vector<int>& R)	
{
	BubbleSort31(R, 0);
}
int main()
{
	// 初始化数组
	vector<int> a = {2, 5, 4, 1, 3};
	
	// 打印数组
	printf("a: "); disp(a);
	
	// 冒泡排序
	printf("排序\n");
	BubbleSort3(a);
	
	// 打印排序结果
	printf("a: "); disp(a);
	
	return 0;
}
